package org.example.myleet.adjacentdifference;

import org.example.myleet.Utils.Assert;
import org.example.myleet.Utils.JsonUtils;
import org.example.myleet.Utils.Parser;

import java.util.*;

/**
 * 差分数组解法
 */
public class AdjacentDifferenceSolution {

    /**
     * 303【差分】区域和检索 - 数组不可变
     */
    static class NumArray {
        int n;
        /**
         * 差分数组
         */
        private long[] diff;
        /**
         * 9 ms
         * 差分数组法
         */
        public NumArray(int[] nums) {
            n = nums.length;
            diff = new long[n];
            if (n > 0) {
                //初始化差分数组
                diff[0] = nums[0];
                for (int i = 1; i < n; i++) {
                    diff[i] = diff[i - 1] + nums[i];
                }
            }
        }
        public int sumRange(int i, int j) {
            if (n == 0) {
                return 0;
            }
            if (i > 0) {
                //i至j的和即差分数组[j]位 - [i-1]位，累计了j位减去累计了i-1位
                return (int) (diff[j] - diff[i-1]);
            }
            return (int) diff[j];
        }
    }

    /**
     * 2251【差分数组+有序集合】花期内花的数目
     */
    public int[] fullBloomFlowers(int[][] flowers, int[] people) {
        //用一个有序集合保存差分数组，从flower[0]到flower[1]进行+1操作，从flower[1]+1到数组结尾进行-1操作
        TreeMap<Integer, Integer> adjDiff = new TreeMap<>(Comparator.naturalOrder());
        for (int[] flower : flowers) {
            adjDiff.merge(flower[0], 1, Integer::sum);
            adjDiff.merge(flower[1] + 1, -1, Integer::sum);
        }
        //由于差分数组的查询需要从头开始逐个遍历得到真实数据，因此需要对people进行排序，从小的位置开始查询
        int[] peopleSorted = new int[people.length];
        System.arraycopy(people, 0, peopleSorted, 0, people.length);
        Arrays.sort(peopleSorted);
        Map<Integer, Integer> answerMap = new HashMap<>(people.length);
        Integer i = 0, flowerCnt = 0;
        while (i < people.length) {
            int p = peopleSorted[i];
            //如果差分数组有序集合不是空的，且查询位置未超过p，需要顺序往下查询超过p位置得到当前flowerCnt
            //差分数组计算第j个位置的结果时取a[j]=a[j-1]+adjDiff[j]
            while (!adjDiff.isEmpty() && adjDiff.firstKey() <= p) {
                flowerCnt += adjDiff.pollFirstEntry().getValue();
            }
            answerMap.put(p, flowerCnt);
            ++i;
        }
        int[] answer = new int[people.length];
        for (i = 0; i < people.length; ++i) {
            answer[i] = answerMap.get(people[i]);
        }
        return answer;
    }

    public static void main(String[] args) {
        AdjacentDifferenceSolution solution = new AdjacentDifferenceSolution();
        Assert.isTrue("[1,2,2,2]".equals(JsonUtils.toJson(solution.fullBloomFlowers(Parser.parse("[[1,6],[3,7],[9,12],[4,13]]"), new int[]{2,3,7,11}))));
    }
}
